/**
 * Find the order<sub>n</sub>(a) for all a < n
 * 
 * @author Jon Ludwig
 */

import java.math.*;
import java.util.*;

public class Order {
	
	/**
	 * Calculates ord_n(a)
	 * 
	 * @param a
	 * @param n
	 * @return
	 */
	public static BigInteger order(BigInteger a, BigInteger n)
	{
		BigInteger ord = BigInteger.ZERO;
		
		// maybe check if gcd(a, n) == 1 ?
		
		BigInteger phi = EulerTotient.phi(n);
		ArrayList<BigInteger> divs = Divisors.divisors(phi);
		
		Collections.sort(divs);
		
		for (BigInteger k : divs)
		{
			//System.out.println("trying " + k);
			if (a.pow(k.intValue()).mod(n).compareTo(BigInteger.ONE) == 0)
			{
				// found a cycle
				ord = k;
				break;
			}
		}
		
		return ord;
	}

	/**
	 * Main entry point.
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		if (args.length < 2) {
			System.out.println("usage: java Order a n");
			return;
		}
		
		BigInteger a = new BigInteger(args[0]);
		BigInteger n = new BigInteger(args[1]);
		
		BigInteger ord = order(a, n);
		
		System.out.println(ord);
	}

}
